package _662;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

import util.TreeNode;

public class S3 {

  class NodePos {
    public TreeNode node;
    public double pos;
    public NodePos(TreeNode node, double pos) {
      this.node = node;
      this.pos = pos;
    }
  }

  public int widthOfBinaryTree(TreeNode root) {
    if (root == null) return 0;
    Queue<NodePos> cur = null;
    Queue<NodePos> next = new LinkedList<NodePos>();
    next.add(new NodePos(root, 0.0));

    int max = 1;
    while (!next.isEmpty()) {
      cur = next;
      next = new LinkedList<NodePos>();
      double leftest = Double.MAX_VALUE;
      double rightest = 0;
      while (!cur.isEmpty()) {
        NodePos nodePos = cur.poll();
        if (nodePos.node.left != null) {
          double posLeft = nodePos.pos * 2;
          next.add(new NodePos(nodePos.node.left, posLeft));
          if (posLeft < leftest) {
            leftest = posLeft;
          }
          if (posLeft > rightest) {
            rightest = posLeft;
          }
        }
        if (nodePos.node.right != null) {
          double posRight = nodePos.pos * 2 + 1;
          next.add(new NodePos(nodePos.node.right, posRight));
          if (posRight < leftest) {
            leftest = posRight;
          }
          if (posRight > rightest) {
            rightest = posRight;
          }
        }
      }
      int width = (int)(rightest - leftest) + 1;
      if (width > max) {
        max = width;
      }
    }

    return max;
  }

private static void test(String[] nums) {
  S3 s = new S3();
  TreeNode tree = TreeNode.constructTree(nums);
  TreeNode.printTree(tree);
  System.out.println("width: " + s.widthOfBinaryTree(tree) + "\n-----------------------------");
}

  public static void main(String[] args) {
    // Test 1
    String[] t1 = {"1", "3", "2", "5", "3", "null", "9"};
    test(t1);

    // Test 2
    String[] t2 = {"1", "3", "null", "5", "3"};
    test(t2);

    // Test 3
    String[] t3 = {"1", "3", "2", "5"};
    test(t3);

    // Test 4
    String[] t4 = {"1", "3", "2", "5", "null", "null", "9", "6", "null", "null", "7"};
    test(t4);

    // Test 5
    String[] t5 = {"0", "null", "0", "null", "0", "null", "0", "null", "0", "0" };
    test(t5);

    //String[] t6 = {"0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","null","0","0"};
    //test(t6);
  }
}